package com.gitee.ty850454.leetcode331;

import java.util.Arrays;

public class Leetcode331 {

    public static void main(String[] args) {
        Leetcode331 instance = new Leetcode331();
        System.out.println(instance.isValidSerialization("9,#,92,#,#"));
        System.out.println(instance.isValidSerialization("1,#,#,#,#"));
        System.out.println(instance.isValidSerialization("9,3,4,#,#,1,#,#,2,#,6,#,#"));
        System.out.println(instance.isValidSerialization("1,#"));
        System.out.println(instance.isValidSerialization("9,#,#,1"));
        System.out.println(instance.isValidSerialization("9,#,1,#,#"));
        System.out.println(instance.isValidSerialization("2,1,#,#,#"));
    }

    public boolean isValidSerialization(String preorder) {
        char[] nodes = preorder.toCharArray();
        char[] stack = new char[nodes.length / 2 + 1];
        int stackTop = -1;
        boolean isNumber = false;

        for (char node : nodes) {
            if (node == ',') {
                isNumber = false;
                continue;
            }
            if (node == '#') {
                while (stackTop > 0 && stack[stackTop] == '#') {
                    if (stack[stackTop - 1] == '#') {
                        return false;
                    }
                    stackTop -= 2;
                }
            } else {
                if (isNumber) {
                    continue;
                }
                isNumber = true;
            }
            stack[++stackTop] = node;
        }
        return stackTop == 0 && stack[0] == '#';
    }

}
